﻿#include "pch.h"
#include "CppUnitTest.h"
#include "../ForTest.h"
#include "../../AlgoInclude/SegmentTreeCall.h"

using namespace Microsoft::VisualStudio::CppUnitTestFramework;

template<class TSave >
class CST : public IRegionCall<TSave>
{
public:
	CST(int N, const TSave& tDefault) :m_tDefault(tDefault) {
		int N2 = 0;
		for (int cnt = 1;cnt < N;N2++, cnt *= 2);
		m_data.assign(N2 + 1, vector<TSave>(N));
	}
	void Init() {
		const int N = m_data[0].size();
		for (int i = 1; i < m_data.size(); i++) {
			const int len = 1 << (i - 1);
			for (int j = 0; j < N; j++) {
				if (j + len >= N) { m_data[i][j] = m_data[i - 1][j]; continue; }
				this->OnUnion(m_data[i][j], m_data[i - 1][j], m_data[i - 1][j + len], j, j + len - 1, min(j + 2 * len, N) - 1);
			}
		}
	}
	TSave QueryByLen(const int& left, const int& len) {
		const int N = m_data[0].size();
		TSave ret = m_tDefault;
		int pos = left;
		for (int i = 0;i < m_data.size();i++) {
			if ((1 << i) & len) {
				this->OnUnion(ret, ret, m_data[i][pos], left, pos - 1, pos + (1 << i) - 1);
				pos += (1 << i);
			}
		}
		return ret;
	}
	vector<vector<TSave>> m_data;
	TSave m_tDefault;
};

namespace multiply
{
	TEST_CLASS(TestMultiply)
	{
		
	public:	
		void Test(vector<int>& par) {
			const int N = par.size();			
			CParents mp(par, N);
			CParentToNeiBo pn(par);
			const int step1 = max(1, N / 100+ N /500 + N /2000);
			const int step2 = max(1, N / 101 + N / 501 + N / 2001);
			auto leves = CBFSLeve::Leve(pn.m_vChild, pn.m_roots);
			for (int i = 0; i < N; i+=step1) {
				for (int q = 1; q <= N - i; q += step2) {
					auto leve = mp.FindEnd(i, leves[i], [&](int mid) {return mid <= i + q; });
					auto gp = mp.GetParent(i, leve);

					auto tmp = i;
					for (; (-1 != tmp) && (tmp <= i + q); tmp = par[tmp]) {
						if ((-1 == par[tmp]) || (par[tmp] > i + q)) { break; }
					}
					std::wstring str = L"i:" + to_wstring(i) + L" q:" + to_wstring(q);
					Assert::AreEqual(tmp, gp, str.c_str());
				}
			}
		}
		TEST_METHOD(TestMethod11)
		{
			int N = 5'000;
			vector<int> par(N);
			for (int i = 0; i < N; i++)
			{
				par[i] = i + 1;
			}
			par.back() = -1;
			Test(par);
		}
		TEST_METHOD(TestMethod2)
		{
			int N = 5'000;
			vector<int> par(N,-1);
			Test(par);
		}
		TEST_METHOD(TestMethod3)
		{
			const int N = 5;
			vector<int> par(N, -1);
			function<void (int)> Tack = [&](int leve) {
				if (N == leve ) {
					Test(par);
					return;
				}
				int pre = 0;
				for (int i = leve+1 ; i < N; i++)
				{
					par[leve] = i;
					Tack(leve + 1);
				}
				par[leve] = -1;
				Tack(leve + 1);
			};
			Tack(0);
		}
	};
	
}
namespace NTreeMultiply {
	TEST_CLASS(LC1483)
	{
		//LC1483. 树节点的第 K 个祖先
		class TreeAncestor {
		public:
			TreeAncestor(int n, vector<int>& parent) :m_pars(parent, n) {

			}

			int getKthAncestor(int node, int k) {
				return m_pars.GetParent(node, k);
			}
			CParents m_pars;
		};
	public:
		TEST_METHOD(TestMethod11)
		{
			int res = 0;
			TreeAncestor treeAncestor(7, vector<int> { -1, 0, 0, 1, 1, 2, 2 });
			res = treeAncestor.getKthAncestor(3, 1);  // 返回 1 ，它是 3 的父节点
			AssertEx(1, res);
			res = treeAncestor.getKthAncestor(5, 2);  // 返回 0 ，它是 5 的祖父节点
			AssertEx(0, res);
			res = treeAncestor.getKthAncestor(6, 3);  // 返回 -1 因为不存在满足要求的祖先节点
			AssertEx(-1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			int res = 0;
			TreeAncestor treeAncestor(5, vector<int> { -1, 0, 0, 0, 3 });
			res = treeAncestor.getKthAncestor(1, 5);  // 返回 1 ，它是 3 的父节点
			AssertEx(-1, res);
			res = treeAncestor.getKthAncestor(3, 2);  // 返回 0 ，它是 5 的祖父节点
			AssertEx(-1, res);
			res = treeAncestor.getKthAncestor(0, 1);  // 返回 -1 因为不存在满足要求的祖先节点
			AssertEx(-1, res);
			res = treeAncestor.getKthAncestor(3, 1);  // 返回 0 ，它是 5 的祖父节点
			AssertEx(0, res);
			res = treeAncestor.getKthAncestor(3, 5);  // 返回 -1 因为不存在满足要求的祖先节点
			AssertEx(-1, res);
		}
	};

	TEST_CLASS(LC2769)
	{
		//【树上倍增 内向基环树 图论 】2836. 在传球游戏中最大化函数值|2769
		class CPow2
		{
		public:
			CPow2(vector<int>& receiver, long long k) : m_c(receiver.size())
			{
				long long tmp = k;
				int iPow2 = 0;
				for (; iPow2 <= 63;iPow2++)
				{
					if ((1LL << iPow2) == tmp)
					{
						break;
					}
					tmp &= ~(1LL << iPow2);
				}
				m_vParent.assign(iPow2 + 1, vector<int>(m_c));
				m_vSum.assign(iPow2 + 1, vector<long long>(m_c));
				for (int i = 0; i < m_c; i++)
				{
					m_vParent[0][i] = receiver[i];
					m_vSum[0][i] = receiver[i];
				}
				for (int j = 1; j <= iPow2; j++)
				{
					for (int i = 0; i < m_c; i++)
					{
						const int next = m_vParent[j - 1][i];
						m_vParent[j][i] = m_vParent[j - 1][next];
						m_vSum[j][i] = m_vSum[j - 1][i] + m_vSum[j - 1][next];
					}
				}
			}
			long long Query(int cur, long long k)
			{
				long long ans = 0;
				for (int i = 0; i < m_vParent.size(); i++)
				{
					if ((1LL << i) & k)
					{
						ans += m_vSum[i][cur];
						cur = m_vParent[i][cur];
					}
				}
				return ans;
			}
			const int m_c;
		protected:
			vector<vector<int>> m_vParent;
			vector<vector<long long>> m_vSum;
		};
		class Solution {
		public:
			long long getMaxFunctionValue(vector<int>& receiver, long long k) {
				CPow2 pow(receiver, k);
				long long llMax = 0;
				for (int i = 0; i < pow.m_c; i++)
				{
					llMax = max(llMax, i + pow.Query(i, k));
				}
				return llMax;
			}
		};
	public:
		vector<int> receiver;
		long long k;
		TEST_METHOD(TestMethod01)
		{
			Solution sln;
			receiver = { 1,0 }, k = 10000000000;
			auto res = sln.getMaxFunctionValue(receiver, k);
			AssertEx(5000000001LL, res);
		}
		TEST_METHOD(TestMethod02)
		{
			Solution sln;
			receiver = { 2, 0, 1 }, k = 4;
			auto res = sln.getMaxFunctionValue(receiver, k);
			AssertEx(6LL, res);
		}
		TEST_METHOD(TestMethod03)
		{
			Solution sln;
			receiver = { 1,1,1,2,3 }, k = 3;
			auto res = sln.getMaxFunctionValue(receiver, k);
			AssertEx(10LL, res);
		}
	};
	
	TEST_CLASS(P2375)
	{
		//【失配树 树上倍增 KMP】P2375 [NOI2014] 动物园|省选-
		class Solution {
		public:
			int Ans(const string s) {
				const int N = s.length();
				auto next = KMP().CalLen(s);
				vector<int> par(N + 1, -1);
				vector<vector<int>> childs(N + 1);
				for (int i = 0; i < N; i++) {
					par[i + 1] = next[i];
					childs[next[i]].emplace_back(i + 1);
				}
				auto leves = CBFSLeve().Leve(childs, { 0 });
				CParents pars(par, N + 1);
				C1097Int<> ans(1);
				for (int i = 1; i <= N; i++) {
					auto Check = [&](int mid) {
						return mid <= i / 2;
					};
					const int cur = pars.FindFirst(i, leves[i], Check);
					ans *= (leves[cur] + 1);
				}
				return ans.ToInt();
			}
		};
	public:
		TEST_METHOD(TestMethod1)
		{
			auto res = Solution().Ans("ab");
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod2)
		{
			auto res = Solution().Ans("aaaaa");
			AssertEx(36, res);
		}
		TEST_METHOD(TestMethod3)
		{
			auto res = Solution().Ans("abcababc");
			AssertEx(32, res);
		}
	};

	TEST_CLASS(P5648)
	{
		//【树上倍增 单调栈】P5648 Mivik的神力|普及+及+
		class CMySparseTable :public CSumSparseTable<long long> {
		public:
			CMySparseTable(int iNodeCnt, long long maxLeve, CParents& p, const vector<int>& a) :CSumSparseTable(iNodeCnt, maxLeve, p), m_a(a) {
				for (int i = 0; i < N; i++) {
					m_data[i][0] = m_a[i] * ((long long)m_p.GetPow2Parent(i, 0) - i);
				}
			}
			const vector<int>& m_a;
		};
		class Solution {
		public:
			vector<long long> Ans(vector<int>& a, vector<pair<int, int>>& query) {
				const int N = a.size();
				vector<int> par(N, -1);
				stack<int> sta;
				for (int i = N - 1; i >= 0; i--) {
					while (sta.size() && (a[i] >= a[sta.top()])) {
						sta.pop();
					}
					if (sta.size()) { par[i] = sta.top(); }
					sta.emplace(i);
				}
				CParentToNeiBo pn(par);
				auto leves = CBFSLeve::Leve(pn.m_vChild, pn.m_roots);
				CParents mp(par, 1 << 19);
				CMySparseTable edgeWSum(N, 1 << 19, mp, a);
				edgeWSum.InitNo0();
				long long lastans = 0;
				vector<long long> ans;
				for (const auto& [u, v] : query) {
					auto t = (u ^ lastans) % N;
					auto q = 1 + (v ^ (lastans + 1)) % (N - t);
					auto leve = mp.FindEnd(t, leves[t], [&](int mid) { return mid <= t + q; });
					int gp = mp.GetParent(t, leve);
					lastans = ((long long)t + q - gp) * a[gp];
					edgeWSum.Query(lastans, t, leve);
					ans.emplace_back(lastans);
				}
				return ans;
			}
		};
	public:
		vector<int> a;
		vector<pair<int, int>> que;
		TEST_METHOD(TestMethod1)
		{
			a = { 1,2,3 }, que = { {1,1},{1,2} };
			auto res = Solution().Ans(a, que);
			AssertEx({ 2,3 }, res);
		}
		TEST_METHOD(TestMethod2)
		{
			a = { 1,2,3 }, que = { {1,1},{1,1} };
			auto res = Solution().Ans(a, que);
			AssertEx({ 2,6 }, res);
		}
	};

	TEST_CLASS(P6148)
	{
		//【树上倍增】P6148 [USACO20FEB] Swapity Swapity Swap S|普及+
		class Solution {
		public:
			vector<int> Ans(const int N, vector < pair<int, int>>& lr, const int K) {
				vector<int> a(N);
				iota(a.begin(), a.end(), 0);
				for (auto [left, r] : lr) {
					left--, r--;
					for (; left < r; left++, r--) {
						swap(a[left], a[r]);
					}
				}
				vector<int> pars(N, -1);
				for (int i = 0; i < N; i++) {
					pars[a[i]] = i;
				}
				CParents mp(pars, K + 1);
				vector<int> endPos(N);
				for (int i = 0; i < N; i++) {
					endPos[i] = mp.GetParent(i, K);
				}
				vector<int> ans(N);
				for (int i = 0; i < N; i++) {
					ans[endPos[i]] = i + 1;
				}
				return ans;
			}
		};
	public:
		int N, K;
		vector < pair<int, int>> lr;
		TEST_METHOD(TestMethod11)
		{
			N = 7, K = 2, lr = { {2,5},{3,7} };
			auto res = Solution().Ans(N, lr, K);
			AssertV({ 1,2,4,3,5,7,6 }, res);
		}
	};

	TEST_CLASS(P6753)
	{
		//【DFS 树上倍增】P6753 [BalticOI 2013] Ball Machine (Day1) 树上倍增 DFS|普及+
		class Solution {
		public:
			vector<int> Ans(const int N, vector<int>& par, vector<pair<int, int>>& query) {
				for (auto& i : par) { i--; }
				for (auto& [kind, num] : query) { if (2 == kind) { num--; } }
				CParentToNeiBo pn(par);
				CParents mp(par, N);
				auto leves = CBFSLeve::Leve(pn.m_vChild, pn.m_roots);
				auto bfsSort = CBFSLeve::LeveSort(leves);
				//BFS模拟DFS,求vMin
				vector<int> vMin(N, INT_MAX / 2);
				for (auto it = bfsSort.rbegin(); it != bfsSort.rend(); ++it) {
					vMin[*it] = min(vMin[*it], *it);
					if (-1 == par[*it]) { continue; }
					vMin[par[*it]] = min(vMin[par[*it]], vMin[*it]);
				}
				for (auto& v : pn.m_vChild) {
					sort(v.begin(), v.end(), [&](int i1, int i2) {return vMin[i1] < vMin[i2]; });
				}
				//DFS求DFS序
				vector<int> vNodeSort(N, -1), vSortToNode;
				function<void(int)> DFS = [&](int cur) {
					if (-1 != vNodeSort[cur]) { return; }
					for (const auto& next : pn.m_vChild[cur]) {
						DFS(next);
					}
					vNodeSort[cur] = vSortToNode.size();
					vSortToNode.emplace_back(cur);
				};
				DFS(pn.m_roots[0]);
				vector<bool> vHas(N);
				priority_queue<int, vector<int>, greater<int>> minHeap;
				for (int i = 0; i < N; i++) {
					minHeap.emplace(i);
				}
				vector<int> ans;
				for (const auto& [kind, num] : query) {
					int cur = -1;
					if (1 == kind) {
						for (int i = 0; i < num; i++) {
							cur = vSortToNode[minHeap.top()];
							minHeap.pop();
							vHas[cur] = true;
						}
						ans.emplace_back(cur + 1);
					}
					else {
						auto Check = [&](int node) {return !vHas[node]; };
						cur = mp.FindFirst(num, leves[num], Check);
						if (-1 == cur)
						{
							cur = mp.GetParent(num, leves[num]);
						}
						else {
							cur = mp.GetParent(num, leves[num] - leves[cur] - 1);
						}
						ans.emplace_back(leves[num] - leves[cur]);
						vHas[cur] = false;
						minHeap.emplace(vNodeSort[cur]);
					}
				}
				return ans;
			}
		};
	public:
		int N;
		vector<int> par;
		string s;
		vector<pair<int, int>> que;
		TEST_METHOD(TestMethod1)
		{
			N = 8, par = { 0,1,2,2,3,3,4,6 }, que = { {1,8},{2,5},{2,7},{2,8} };
			auto res = Solution().Ans(N, par, que);
			AssertEx({ 1,3,2,2 }, res);
		}
		TEST_METHOD(TestMethod2)
		{
			N = 2, par = { 2,0 }, que = { {1,2} };
			auto res = Solution().Ans(N, par, que);
			AssertEx({ 2 }, res);
		}
	};

	TEST_CLASS(P6902)
	{
		//【链 树上倍增 贪心】P6902 [ICPC 2014 WF] Surveillance|普及+
		class Solution {
		public:
			int Ans(const int N, vector<pair<int, int>>& rang) {
				for (auto& [left, r] : rang) {
					if (r < left) { r += N; }
					left--, r--;
				}
				sort(rang.begin(), rang.end(), greater<>());
				vector<int> par(2 * N + 1, -1);
				int iMax = -1;
				for (int i = 0; i < 2 * N; i++) {
					while (rang.size() && (rang.back().first <= i)) {
						iMax = max(iMax, rang.back().second);
						rang.pop_back();
					}
					if (iMax >= i) {
						par[i] = iMax + 1;
					}
				}
				const auto& neiBo = CParentToNeiBo(par).m_vChild;
				vector<int> inDeg(2 * N + 1);
				for (const auto& v : neiBo) {
					for (const int i : v) {
						inDeg[i]++;
					}
				}
				vector<int> vDeg0;
				for (int i = 0; i < inDeg.size(); i++) {
					if (0 == inDeg[i]) { vDeg0.emplace_back(i); }
				}
				auto leves = CBFSLeve::Leve(neiBo, vDeg0);
				int ans = INT_MAX / 2;
				CParents mp(par, 2 * N + 1);
				for (int i = 0; i < N; i++) {
					auto Check = [&](int node) {
						return node >= i + N;
					};
					auto pa = mp.FindFirst(i, leves[i], Check);
					if (-1 == pa) { continue; }
					ans = min(ans, leves[i] - leves[pa]);
				}
				return (INT_MAX / 2 == ans) ? -1 : ans;
			}
		};
	public:
		int n;
		vector<pair<int, int>> rang;
		TEST_METHOD(TestMethod1)
		{
			n = 100, rang = { {1,50},{50,70},{70,90},{90,40},{20,60},{60,80},{80,20} };
			auto res = Solution().Ans(n, rang);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod2)
		{
			n = 8, rang = { {8,3},{5,7} };
			auto res = Solution().Ans(n, rang);
			AssertEx(-1, res);
		}
		TEST_METHOD(TestMethod3)
		{
			n = 8, rang = { {8,4},{5,7} };
			auto res = Solution().Ans(n, rang);
			AssertEx(2, res);
		}
	};

	TEST_CLASS(P7167)
	{
		//【树上倍增 ST表】P7167 [eJOI 2020] Fountain (Day1)|省选-		

		class Solution {
		public:
			vector<int> Ans(vector<pair<int, int>>& dc, vector<pair<int, int>>& query) {
				const int N = dc.size();
				vector<int> par(N, -1);
				stack<int> sta;
				for (int i = N - 1; i >= 0; i--) {
					while (sta.size() && (dc[i].first >= dc[sta.top()].first)) {
						sta.pop();
					}
					if (sta.size()) { par[i] = sta.top(); }
					sta.emplace(i);
				}
				CParentToNeiBo pn(par);
				auto leves = CBFSLeve::Leve(pn.m_vChild, pn.m_roots);
				CParents mp(par, N);
				CSumSparseTable<long long> edgeWSum(N, N, mp);
				for (int i = 0; i < N; i++) {
					edgeWSum.m_data[i][0] = dc[i].second;
				}
				edgeWSum.InitNo0();
				vector<int> ans;
				for (auto [r, v] : query) {
					r--;
					auto cur = edgeWSum.MoreEqual(r, v);
					if (-1 == cur) {
						ans.emplace_back(0);
					}
					else {
						cur = mp.GetParent(r, cur);
						ans.emplace_back(cur + 1);
					}
				}
				return ans;
			}
		};
	public:
		vector<pair<int, int>> dc, que;
		TEST_METHOD(TestMethod1)
		{
			dc = { {4,10},{6,8},{3,5},{4,14},{10,9},{4,20} }, que = { {1,25},{6,30},{5,8},{3,13},{2,8} };
			auto res = Solution().Ans(dc, que);
			AssertEx({ 5,0,5,4,2 }, res);
		}
	};
	
	TEST_CLASS(P9185)
	{
		//【树上倍增】P9185 [USACO23OPEN] Rotate and Shift B|普及+
		class Solution {
		public:
			vector<int> Ans(const int N, int T, vector<int>& A) {
				vector<int> r(N), left(N), d(N);
				for (int i = 0; i < N; i++) {
					r[i] = (i + 1) % N;
					left[i] = (i - 1) % N;
					if (left[i] < 0) { left[i] += N; }
					d[i] = i;
				}
				for (int i = 0; i < A.size(); i++) {
					d[A[i]] = A[(i + 1) % A.size()];
				}
				vector<int> s(N);
				for (int i = 0; i < N; i++) {
					s[i] = left[d[i]];
				}
				vector<int> ans(N);
				CParents mp(s, T), mp2(r, T);
				for (int i = 0; i < N; i++) {
					const int i1 = mp.GetParent(i, T);
					ans[mp2.GetParent(i1, T)] = i;
				}
				return ans;
			}
		};
	public:
		vector<int>A;
		TEST_METHOD(TestMethod01)
		{
			A = { 0,2,3 };
			auto res = Solution().Ans(5, 1, A);
			AssertV({ 3,1,0,2,4 }, res);
		}
		TEST_METHOD(TestMethod02)
		{
			A = { 0,2,3 };
			auto res = Solution().Ans(5, 2, A);
			AssertV({ 3,4,0,1,2 }, res);
		}
		TEST_METHOD(TestMethod03)
		{
			A = { 0,2,3 };
			auto res = Solution().Ans(5, 3, A);
			AssertV({ 2,4,3,1,0 }, res);
		}
		TEST_METHOD(TestMethod04)
		{
			A = { 0,2,3 };
			auto res = Solution().Ans(5, 4, A);
			AssertV({ 1,2,3,4,0 }, res);
		}
	};
	TEST_CLASS(P9246)
	{
		//【树上倍增】P9246 [蓝桥杯 2023 省 B] 砍树|普及+
		class Solution {
		public:
			int Ans(const int N, vector<pair<int, int>>& edge, vector<pair<int, int>>& ab) {
				const int M = ab.size();
				for (auto& [u, v] : edge) {
					u--, v--;
				}
				for (auto& [a, b] : ab) { a--; b--; }
				auto neiBo = CNeiBo::Two(N, edge, false);
				auto leves = CBFSLeve::Leve(neiBo, { 0 });
				auto leveNodes = CBFSLeve::LeveNodes(leves);
				vector<int> par(N, -1);
				for (auto& [u, v] : edge) {
					if (leves[u] > leves[v]) {
						swap(u, v);
					}
					par[v] = u;
				}
				C2Parents pars(par, leves);
				vector<int> diff(N);
				for (const auto& [a, b] : ab) {
					const int ab = pars.GetPublicParent(a, b);
					diff[a]++; diff[b]++; diff[ab] -= 2;
				}
				vector<bool> canDel(N);
				for (auto it = leveNodes.rbegin(); it != leveNodes.rend(); ++it) {
					for (const auto& cur : *it) {
						canDel[cur] = M == diff[cur];
						const int iPar = par[cur];
						if (-1 == iPar) { continue; }
						diff[iPar] += diff[cur];
					}
				}
				for (int i = edge.size(); i >= 1;i--) {
					if (canDel[edge[i - 1].second]) { return i; }
				}
				return -1;
			}
		};
	public:
		int N;
		vector<pair<int, int>> edge;
		vector<pair<int, int>>ab;
		TEST_METHOD(TestMethod01)
		{
			N = 6, edge = { {1,2},{2,3},{4,3},{2,5},{6,5} }, ab = { {3,6},{4,5} };
			auto res = Solution().Ans(N, edge, ab);
			AssertEx(4, res);
		}
	};

	TEST_CLASS(P10931)
	{
		//【LCA 树上差分】P10931 闇の連鎖||普及+
		class Solution {
		public:
			int Ans(const int N, vector<pair<int, int>>& edge, vector<pair<int, int>>& edge2) {		
				//下标从0开始
				for (auto& [u, v] : edge) { u--, v--; }
				for (auto& [u, v] : edge2) { u--, v--; }
				auto neiBo = CNeiBo::Two(N, edge, false, 0);
				auto leves = CBFSLeve::Leve(neiBo, { 0 });
				vector<int> vPar(N, -1);
				for (auto [u, v] : edge) {
					if (leves[u] < leves[v]) {
						swap(u, v);
					}
					vPar[u] = v;
				}
				C2Parents mp(vPar, leves);
				vector<int> cnt(N), cnt2(N);
				for (auto& [u, v] : edge2)
				{
					const int g = mp.GetPublicParent(u, v);
					cnt2[u]++, cnt2[v]++, cnt2[g] -= 2;
				}
				auto nodes = CBFSLeve::LeveSort(leves);
				for (auto it = nodes.rbegin();it != nodes.rend();++it) {
					cnt[*it] = cnt2[*it];
					if (-1 != vPar[*it]) {
						cnt2[vPar[*it]] += cnt[*it];
					}
				}
				int ans = 0;
				for (int i = 1;i < N;i++) {
					if (1 == cnt[i]) {
						ans++;
					}
					else if (0 == cnt[i]) {
						ans += edge2.size();
					}
				}
				return ans;
			}
		};
	public:
		int N;
		vector<pair<int, int>> edge,edge2;
		TEST_METHOD(TestMethod01)
		{
			N = 4, edge = { {1,2},{2,3},{1,4} }, edge2 = { {3,4} };
			auto res = Solution().Ans(N, edge, edge2);
			AssertEx(3, res);
		}
	};

	TEST_CLASS(P11267)
	{
		//【树上倍增 滑动窗口】P11267 【MX-S5-T1】王国边缘|普及+
		typedef C1097Int<> BI;
		class Solution {
		public:
			vector<int> Ans(const int N, const long long M, string& s, vector<pair<long long, long long>>& query) {
				vector<long long> next(N, -1);
				long long r = M;
				long long left = (M < N) ? 1 : (M - (N - 1));
				deque<long long> dque;
				for (auto j = left; j <= r; j++) {
					if ('1' != s[j % N]) { continue; }
					dque.emplace_back(j);
				}
				for (int i = 0; i < N; i++) {
					if (dque.size()) {
						next[i] = dque.back();
					}
					else {
						next[i] = i + 1;
					}
					if ('1' == s[left % N]) { dque.pop_front(); } left++;
					r++; if ('1' == s[r % N]) { dque.push_back(r); }
				}
				vector<int> par(N, -1); vector<vector<BI>> dis(N, vector<BI>(62));
				for (int i = 0; i < N; i++) {
					par[i] = next[i] % N;
					dis[i][0] = BI(next[i] - i);
				}
				CParents mp(par, LLONG_MAX / 2);
				for (int j = 1; j < 62; j++) {
					for (int i = 0; i < N; i++) {
						dis[i][j] = dis[i][j - 1] + dis[mp.GetPow2Parent(i, j - 1)][j - 1];
					}
				}
				vector<int> ans;
				for (auto [start, k] : query) {
					int s = (start - 1) % N;
					BI cur(start);
					for (int i = 61; i >= 0; i--) {
						if ((1LL << i) & k) {
							cur += BI(dis[s][i]);
							s = mp.GetPow2Parent(s, i);
						}
					}
					ans.emplace_back(cur.ToInt());
				}
				return ans;
			}
		};
	public:
		int N;
		long long M;
		string s;
		vector<pair<long long, long long>> que;
		TEST_METHOD(TestMethod1)
		{
			N = 8, M = 3, s = "10001011", que = { {1,2},{4,3} };
			auto res = Solution().Ans(N, M, s, que);
			AssertEx({ 5,10 }, res);
		}
	};
	TEST_CLASS(P11477)
	{
		//【图论 树上倍增】P11477 [COCI 2024/2025 #3] 林卡树 / Stablo|普及+
		class Solution {
		public:
			vector<long long> Ans(vector<int>& ws, vector<int>& ps, vector<pair<int, int>>& ope) {
				const int N = ws.size();
				vector<vector<int>> vChild(N);
				for (int i = 0; i < ps.size(); i++) {
					vChild[ps[i] - 1].emplace_back(1 + i);
					ps[i]--;
				}
				ps.insert(ps.begin(), -1);
				CParents mp(ps, N);
				auto leves = CBFSLeve::Leve(vChild, { 0 });
				auto nodes = CBFSLeve::LeveSort(leves);
				vector<long long> fs(N), wss(N);
				for (auto it = nodes.rbegin(); it != nodes.rend(); ++it) {
					wss[*it] = ws[*it];
					for (const auto& i : vChild[*it]) {
						wss[*it] += wss[i];
						fs[*it] += wss[i] + fs[i];
					}
				}
				vector<long long> ans;
				for (auto [x, y] : ope) {
					x--, y--;
					const int z = mp.GetParent(x, leves[x] - leves[y] - 1);
					long long add = 0;
					if (z != y) {
						add = wss[z] - wss[x] - (leves[x] - leves[y] - 1) * ws[x];
					}
					ans.emplace_back(fs[y] + add);
				}
				return ans;
			}
		};
	public:
		vector<int> ws, ps;
		vector<pair<int, int>> ope;
		TEST_METHOD(TestMethod01)
		{
			ws = { 1,2,3 }, ps = { 1,2 }, ope = { {3,1} };
			auto res = Solution().Ans(ws, ps, ope);
			AssertV({ 7 }, res);
		}
		TEST_METHOD(TestMethod02)
		{
			ws = { 4,5,6 }, ps = { 1,1 }, ope = { {2,1},{3,1} };
			auto res = Solution().Ans(ws, ps, ope);
			AssertV({ 11,11 }, res);
		}
		TEST_METHOD(TestMethod03)
		{
			ws = { 2,5,2,2,2 }, ps = { 1,2,3,2 }, ope = { {4,3},{3,2},{5,1} };
			auto res = Solution().Ans(ws, ps, ope);
			AssertV({ 2,8,26 }, res);
		}
	};
	TEST_CLASS(P6041)
	{
		//【DFS序 树上倍增】P6041 「ACOI2020」布丁暗杀计划|省选-
		class Solution {
		public:
			vector<long long> Ans(vector<int>& colors, vector<int>& ds, vector<int> par, vector<pair<int, int>>& uk) {
				const int N = colors.size();
				const int M = *max_element(colors.begin(), colors.end());
				//下标改成0
				for (auto& p : par) {
					p--;
				}
				par.insert(par.begin(), -1);
				for (auto& [u, k] : uk) { u--; }
				vector<vector<int>> vChild(N);
				for (int i = 1;i < N;i++) {
					vChild[par[i]].emplace_back(i);
				}
				vector<int> vSort(N), vLeve(N), vEndSort(N),vSortToNode(N);
				int iTime = 0;
				function<void(int, int)> DFS = [&](int cur, int leve) {
					vSortToNode[iTime] = cur;
					vSort[cur] = iTime++;
					vLeve[cur] = leve;
					for (const auto& chi : vChild[cur]) {
						DFS(chi, leve + 1);
					}
					vEndSort[cur] = iTime-1;
				};
				DFS(0, 0);
				CParents mp(par, N);
				vector<unordered_map<int, vector<int>>> vm(M + 1);
				for (int i = 0;i < N; i++) {
					vm[colors[i]][vLeve[i]].emplace_back(vSort[i]);
				}
				vector<unordered_map<int, vector<long long>>> vmPre(M + 1);
				for (int c = 1; c <= M;c++) {
					for (auto& [leve, v] : vm[c]) {
						sort(v.begin(), v.end());
						auto& pre = vmPre[c][leve];
						pre = { 0 };
						for (const auto& s : v) {
							pre.emplace_back(pre.back()+ds[vSortToNode[s]]);
						}
					}
				}
				vector<long long> ans;
				for (const auto& [u, k] : uk) {
					const int g = mp.GetParent(u, k);
					if (-1 == g) { ans.emplace_back(0);continue; }
					auto& v = vm[colors[g]][vLeve[u]];
					if (!vmPre[colors[g]].count(vLeve[u])) { ans.emplace_back(0); continue; }
					auto& pre = vmPre[colors[g]][vLeve[u]];
					auto inx1 = lower_bound(v.begin(), v.end(), vSort[g])-v.begin();
					auto inx2 = upper_bound(v.begin(), v.end(), vEndSort[g]) - v.begin();
					ans.emplace_back(pre[inx2] - pre[inx1]);
				}
				return ans;
			}
		};

	public:
		vector<int> colors, ds,pars;
		vector<pair<int, int>> uk;
		TEST_METHOD(TestMethod01)
		{
			colors = { 1,1,1 }, ds = { 1,2,3 }, pars = { 1,1 }, uk = { {2,1},{2,100} };
			auto res = Solution().Ans(colors, ds, pars, uk);
			AssertV({ 5 ,0}, res);
		}
		TEST_METHOD(TestMethod02)
		{
			colors = { 1,2,2,1,1 }, ds = { 1,5,2,4,2 }, pars = { 1,1,2,3 }, uk = { {3,1},{4,2},{5,1} };
			auto res = Solution().Ans(colors, ds, pars, uk);
			AssertV({0,6,0 }, res);
		}
	};
}
namespace NLCA {

	TEST_CLASS(LC2846)
	{
		//【深度优先 树上倍增 】2846. 边权重均等查询|2508
		class CPubSum
		{
		public:
			CPubSum(vector<int>& vQual, CParents& calPar, const int iQua, const int iMaxDepth) :m_calPar(calPar)
			{
				int iBitNum = 0;
				for (; (1 << iBitNum) < iMaxDepth; iBitNum++);
				m_vSum.assign(iBitNum + 1, vector<int>(vQual.size()));
				for (int i = 0; i < vQual.size(); i++)
				{
					m_vSum[0][i] = (iQua == vQual[i]);
				}
				for (int iBit = 1; iBit < m_vSum.size(); iBit++)
				{
					for (int i = 0; i < vQual.size(); i++)
					{
						const int next = calPar.GetParent(i, 1 << (iBit - 1));
						if (-1 == next)
						{
							continue;
						}
						m_vSum[iBit][i] = m_vSum[iBit - 1][i] + m_vSum[iBit - 1][next];
					}
				}
			}
			int Sum(int cur, int cnt)
			{
				int iRet = 0;
				for (int iBit = 0; iBit < m_vSum.size(); iBit++)
				{
					if ((1 << iBit) & cnt)
					{
						iRet += m_vSum[iBit][cur];
						cur = m_calPar.GetParent(cur, 1 << iBit);
					}
				}
				return iRet;
			}
			vector<vector<int>> m_vSum;
			CParents& m_calPar;
		};
		class Solution {
		public:
			vector<int> minOperationsQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {
				m_vDepth.resize(n);
				m_vParent.resize(n);
				m_vQual.resize(n);
				auto vNeiBo = CNeiBo::Three(n, edges, false);
				DFS(0, -1, vNeiBo, 0);
				C2Parents pubParent(m_vParent, m_vDepth);
				vector<CPubSum*> vPubSum;
				const int iMaxDepth = *std::max_element(m_vDepth.begin(), m_vDepth.end());
				for (int i = 1; i <= 26; i++)
				{
					vPubSum.emplace_back(new CPubSum(m_vQual, pubParent, i, iMaxDepth));
				}
				vector<int> vRet;
				for (const auto& v : queries)
				{
					int pub = pubParent.GetPublicParent(v[0], v[1]);
					int iMin = INT_MAX;
					for (int i = 0; i < 26; i++)
					{
						int iCnt1 = m_vDepth[v[0]] - m_vDepth[pub];
						int iCnt2 = m_vDepth[v[1]] - m_vDepth[pub];
						const int cur = iCnt1 + iCnt2 - vPubSum[i]->Sum(v[0], iCnt1) - vPubSum[i]->Sum(v[1], iCnt2);
						iMin = min(iMin, cur);
					}
					vRet.emplace_back(iMin);
				}
				return vRet;
			}
			void DFS(int cur, int par, vector < vector<pair<int, int>>>& vNeiBo, int iQua)
			{
				m_vParent[cur] = par;
				m_vDepth[cur] = (-1 == par) ? 0 : (m_vDepth[par] + 1);
				m_vQual[cur] = iQua;
				for (const auto& [next, qua] : vNeiBo[cur])
				{
					if (next == par)
					{
						continue;
					}
					DFS(next, cur, vNeiBo, qua);
				}
			}
			vector<int> m_vDepth, m_vParent, m_vQual;
		};
	public:
		int n;
		vector<vector<int>> edges, queries;
		TEST_METHOD(TestMethod01)
		{
			Solution sln;
			n = 7, edges = { {0,1,1},{1,2,1},{2,3,1},{3,4,2},{4,5,2},{5,6,2} }, queries = { {0,3},{3,6},{2,6},{0,6} };
			auto res = sln.minOperationsQueries(n, edges, queries);
			AssertEx({ 0,0,1,3 }, res);
		}
		TEST_METHOD(TestMethod02)
		{
			Solution sln;
			n = 8, edges = { {1,2,6},{1,3,4},{2,4,6},{2,5,3},{3,6,6},{3,0,8},{7,0,2} }, queries = { {4,6},{0,4},{6,5},{7,4} };
			auto res = sln.minOperationsQueries(n, edges, queries);
			AssertEx({ 1,2,2,3 }, res);
		}
	};

	TEST_CLASS(LC3067)
	{
		//【树上倍增】【割点】 【换根法】3067. 在带权树网络中统计可连接服务器对数目|1909
		class Solution {
		public:
			vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {
				m_c = edges.size() + 1;
				m_vDisToRoot.resize(m_c);
				m_vParent.resize(m_c);
				m_vLeve.resize(m_c);
				auto neiBo = CNeiBo::Three(m_c, edges, false, 0);
				DFS(neiBo, 0, -1, 0, 0);
				C2Parents par(m_vParent, m_vLeve);
				vector<int> vRet(m_c);
				for (int c = 0; c < m_c; c++)
				{
					CUnionFind uf(m_c);
					for (const auto& v : edges)
					{
						if ((v[0] == c) || (v[1] == c))
						{
							continue;
						}
						uf.Union(v[0], v[1]);
					}
					vector<int> vRegionCnt(m_c);
					for (int ab = 0; ab < m_c; ab++)
					{
						if (ab == c)
						{
							continue;
						}
						const int pub = par.GetPublicParent(ab, c);
						const int len = m_vDisToRoot[ab] + m_vDisToRoot[c] - 2 * m_vDisToRoot[pub];
						if (0 != len % signalSpeed)
						{
							continue;
						}
						vRegionCnt[uf.GetConnectRegionIndex(ab)]++;
					}
					int& iRet = vRet[c];
					const int total = std::accumulate(vRegionCnt.begin(), vRegionCnt.end(), 0);
					for (int c1 = 0; c1 < m_c; c1++)
					{
						iRet += vRegionCnt[c1] * (total - vRegionCnt[c1]);
					}
					iRet /= 2;
				}
				return vRet;
			}
			void DFS(vector<vector<std::pair<int, int>>>& neiBo, int cur, int par, int leve, int dis)
			{
				m_vDisToRoot[cur] = dis;
				m_vParent[cur] = par;
				m_vLeve[cur] = leve;
				for (const auto& [next, len] : neiBo[cur])
				{
					if (next == par)
					{
						continue;
					}
					DFS(neiBo, next, cur, leve + 1, dis + len);
				}
			}
			vector<int> m_vDisToRoot, m_vParent, m_vLeve;
			int m_c;
		};
	public:
		vector<vector<int>> edges;
		int signalSpeed;
		TEST_METHOD(TestMethod01)
		{
			Solution sln;
			edges = {  }, signalSpeed = 1;
			auto res = sln.countPairsOfConnectableServers(edges, signalSpeed);
			AssertEx({ 0 }, res);
		}
		TEST_METHOD(TestMethod02)
		{
			Solution sln;
			edges = { {0,1,1} }, signalSpeed = 1;
			auto res = sln.countPairsOfConnectableServers(edges, signalSpeed);
			AssertEx({ 0,0 }, res);
		}
		TEST_METHOD(TestMethod03)
		{
			Solution sln;
			edges = { {0,1,1},{1,2,1} }, signalSpeed = 1;
			auto res = sln.countPairsOfConnectableServers(edges, signalSpeed);
			AssertEx({ 0,1,0 }, res);
		}
		TEST_METHOD(TestMethod04)
		{
			Solution sln;
			edges = { {0,1,1},{1,2,5},{2,3,13},{3,4,9},{4,5,2} }, signalSpeed = 1;
			auto res = sln.countPairsOfConnectableServers(edges, signalSpeed);
			AssertEx({ 0,4,6,6,4,0 }, res);
		}
		TEST_METHOD(TestMethod05)
		{
			Solution sln;
			edges = { {0,6,3},{6,5,3},{0,3,1},{3,2,7},{3,1,6},{3,4,2} }, signalSpeed = 3;
			auto res = sln.countPairsOfConnectableServers(edges, signalSpeed);
			AssertEx({ 2,0,0,0,0,0,2 }, res);
		}
	};

	TEST_CLASS(P3398)
	{
		//P3398 仓鼠找 sugar
		class Solution {
		public:
			vector<bool> Ans(vector<pair<int, int>>& edge, vector<tuple<int, int, int, int>>& que) {
				const int N = edge.size() + 1;
				auto neiBo = CNeiBo::Two(N, edge, false, 1);
				auto leves = CBFSLeve::Leve(neiBo, { 0 });
				vector<int> pars(N, -1);
				for (int i = 0; i < N; i++) {
					for (const auto& j : neiBo[i]) {
						if (leves[j] < leves[i]) { continue; }
						pars[j] = i;
					}
				}
				C2Parents par2s(pars, leves);
				auto Is2 = [&](int b, int f) {
					const int iSubLeve = leves[b] - leves[f];
					if (iSubLeve < 0) { return false; }
					return par2s.GetParent(b, iSubLeve) == f;
				};
				auto Is = [&](int a, int b, int c, int d) {
					auto e = par2s.GetPublicParent(a, b);
					auto f = par2s.GetPublicParent(c, d);
					if (leves[e] > leves[f]) {
						swap(a, c);
						swap(b, d);
						swap(e, f);
					}
					return Is2(a, f) || Is2(b, f);
				};
				vector<bool> ans;
				for (const auto& [a, b, c, d] : que) {
					ans.emplace_back(Is(a - 1, b - 1, c - 1, d - 1));
				}
				return ans;
			}
		};
	public:
		vector<pair<int, int>> edge;
		vector<tuple<int, int, int, int>> que;
		TEST_METHOD(TestMethod1)
		{
			edge = { {1,2},{1,3},{1,4},{1,5} }, que = { {2,3,4,5} };
			auto res = Solution().Ans(edge, que);
			AssertEx({ true }, res);
		}
		TEST_METHOD(TestMethod2)
		{
			edge = { {1,2},{2,3},{2,4},{2,5},{1,6} }, que = { {3,6,4,5},{4,5,3,6} };
			auto res = Solution().Ans(edge, que);
			AssertEx({ true,true }, res);
		}
		TEST_METHOD(TestMethod11)
		{
			edge = { {2,5},{4,2},{1,3},{1,4} }, que = { {5,1,5,1},{2,2,1,4},{4,1,3,4},{3,1,1,5},
				{3,5,1,4} };
			auto res = Solution().Ans(edge, que);
			AssertEx({ true,false,true,true,true }, res);
		}
	};

	TEST_CLASS(P4281)
	{
		//【树上倍增】P4281 [AHOI2008] 紧急集合 / 聚会|普及+
		class Solution {
		public:
			vector<pair<int, int>> Ans(const int N, vector<pair<int, int>>& edge, vector<tuple<int, int, int>>& query) {
				auto neiBo = CNeiBo::Two(N, edge, false, 1);
				auto leves = CBFSLeve::Leve(neiBo, { 0 });
				vector<int> par(N, -1);
				for (auto [u, v] : edge) {
					u--, v--;
					if (leves[u] < leves[v]) { par[v] = u; }
					else { par[u] = v; }
				}
				C2Parents mp(par, leves);
				auto Len = [&](int e, int f) {
					const int g = mp.GetPublicParent(e, f);
					return leves[e] - leves[g] + leves[f] - leves[g];
				};
				vector<pair<int, int>> ans;
				for (auto [x, y, z] : query) {
					x--, y--, z--;
					const int D1 = mp.GetPublicParent(x, y);
					const int D2 = mp.GetPublicParent(y, z);
					const int D3 = mp.GetPublicParent(z, x);
					int D = D3;
					if (D1 == D3) { D = D2; }
					else if (D2 == D3) { D = D1; }
					ans.emplace_back(D + 1, Len(x, D) + Len(y, D) + Len(z, D));
				}
				return ans;
			}
		};
	public:
		int N;
		vector<pair<int, int>> edge;
		vector< tuple<int, int, int>> que;
		TEST_METHOD(TestMethod1)
		{
			N = 6, edge = { {1,2},{2,3},{2,4},{4,5},{5,6} }, que = { {4,5,6},{6,3,1},{2,4,4},{6,6,6} };
			auto res = Solution().Ans(N, edge, que);
			auto act = vector<pair<int, int>>{ { 5, 2 }, { 2,5 }, { 4,1 }, { 6,0 } };
			AssertV(act, res);
		}
	};
	
	TEST_CLASS(P9245)
	{
		//【LCA 树上倍增】P9245 [蓝桥杯 2023 省 B] 景区导游|普及+
		class Solution {
		public:
			vector<long long> Ans(const int N, vector<tuple<int, int, int>>& edge, vector<int>& A) {
				const int K = A.size();
				vector<vector<int>> neiBo(N);
				for (auto& [u, v, t] : edge) {
					u--, v--;
					neiBo[u].emplace_back(v);
					neiBo[v].emplace_back(u);
				}
				for (auto& i : A) { i--; }
				auto leves = CBFSLeve::Leve(neiBo, { 0 });
				auto leveNodes = CBFSLeve::LeveNodes(leves);
				vector<int> par(N, -1), w1(N);
				vector<long long> w(N);
				for (auto& [u, v, t] : edge) {
					if (leves[u] > leves[v]) {
						swap(u, v);
					}
					par[v] = u;
					w1[v] = t;
				}
				for (const auto& v : leveNodes) {
					for (const auto& cur : v) {
						if (-1 == par[cur]) { continue; }
						w[cur] = w[par[cur]] + w1[cur];
					}
				}
				C2Parents pars(par, leves);
				auto Dis = [&](int a, int b) {
					const auto ab = pars.GetPublicParent(a, b);
					return w[a] + w[b] - 2 * w[ab];
				};
				long long S = 0;
				for (int i = 1; i < A.size(); i++) {
					S += Dis(A[i], A[i - 1]);
				}
				vector<long long> ans;
				ans.emplace_back(S - Dis(A[0], A[1]));
				for (int i = 1; i + 1 < A.size(); i++) {
					long long tmp = Dis(A[i - 1], A[i + 1]) - Dis(A[i - 1], A[i]) - Dis(A[i], A[i + 1]);
					ans.emplace_back(S + tmp);
				}
				ans.emplace_back(S - Dis(A[K - 1], A[K - 2]));
				return ans;
			}
		};
	public:
		int N;
		vector<tuple<int, int, int>> edge;
		vector<int>A;
		TEST_METHOD(TestMethod01)
		{
			N = 6, edge = { {1,2,1},{1,3,1},{3,4,2},{3,5,2},{4,6,3} }, A = { 2,6,5,1 };
			auto res = Solution().Ans(N, edge, A);
			AssertV({ 10,7,13,14 }, res);
		}
	};

	TEST_CLASS(P9487)
	{
		//图论 LCA BFS DFS】P9487 「LAOI-1」小熊游景点|普及+
		template<class TSave>
		class CMultMin {
		public:
			CMultMin(const vector<int>& next, CParents& pars, const vector<TSave>& vals) :m_vNext(next), m_pars(pars) {
				const int N = next.size();
				const int M = pars.GetBitCnt();
				m_data.assign(N, vector<TSave>(M));
				for (int i = 0; i < N; i++) {
					m_data[i][0] = vals[i];
				}
				for (int i = 0; i + 1 < M; i++) {
					const int len = 1 << i;
					for (int j = 0; j < N; j++) {
						m_data[j][i + 1] = m_data[j][i];
						int j2 = pars.GetPow2Parent(j, i);
						if (-1 != j2) {
							m_data[j][i + 1] = min(m_data[j][i], m_data[j2][i]);
						}
					}
				}
			}
			TSave Query(int cur, int len, TSave def) {
				for (int iBit = 0; iBit < m_data[0].size(); iBit++)
				{
					if (len & (1 << iBit))
					{
						def = min(def, m_data[cur][iBit]);
						cur = m_pars.GetPow2Parent(cur, iBit);
						if (-1 == cur) { return def; }
						len -= (1 << iBit);
					}
				}
				return def;
			};
			const vector<int>& m_vNext;
			vector<vector<TSave>> m_data;
			CParents& m_pars;
		};

		class Solution {
		public:
			vector<long long> Ans(vector<int>& pw, vector<tuple<int, int, int>>& edge, vector<pair<int, int>>& que) {
				const int N = pw.size();
				vector<vector<int>> neiBo(N);
				for (auto& [n1, n2, w] : edge) {
					n1--, n2--;
				}
				for (auto& [a, b] : que) {
					a--, b--;
				}
				for (const auto& [n1, n2, w] : edge) {
					neiBo[n1].emplace_back(n2);
					neiBo[n2].emplace_back(n1);
				}
				auto leves = CBFSLeve::Leve(neiBo, { 0 });
				vector<int> pars(N, -1), ew(N);//pars[cur]记录cur父节点，ew[cur]记录边cur、pars[cur]的权。
				for (int i = 0; i < N; i++) {
					for (const auto& j : neiBo[i]) {
						if (leves[j] < leves[i]) { continue; }
						pars[j] = i;
					}
				}
				for (const auto& [n1, n2, w] : edge) {
					if (leves[n1] < leves[n2]) {
						ew[n2] = w;
					}
					else {
						ew[n1] = w;
					}
				}
				auto nodeByLeveSort = CBFSLeve::LeveSort(leves);
				vector<long long> pw0(pw.begin(), pw.end()), ew0(N);//d[i]记录i到0的简单路径的点权之和，e记录边权。
				for (const auto& node : nodeByLeveSort)
				{
					if (-1 == pars[node]) { continue; }
					pw0[node] += pw0[pars[node]];
					ew0[node] += ew0[pars[node]];
				}
				vector<vector<tuple<long long, long long, int>>> pc(N);
				vector<pair<long long, long long>> pp(N);
				for (int cur = 0; cur < N; cur++) {
					pp[cur] = make_pair(0, -pw[cur]);
					pc[cur].emplace_back(make_tuple(0, -pw[cur], -1));
				}
				for (auto it = nodeByLeveSort.rbegin(); it != nodeByLeveSort.rend(); ++it) {
					auto& v = pc[*it];
					if (v.size() > 1) {//只保留最优次优
						nth_element(v.begin(), v.begin() + 1, v.end());
						v.erase(v.begin() + 2, v.end());
					}
					const auto& t = pc[*it].front();
					if (-1 == pars[*it]) { continue; }
					pc[pars[*it]].emplace_back(make_tuple(get<0>(t) + ew[*it], get<1>(t) - pw[*it] - pw[pars[*it]], *it));
				}
				for (const auto& cur : nodeByLeveSort)
				{
					const int iPar = pars[cur];
					if (-1 == iPar) { continue; }
					auto t = make_pair(ew[cur] + get<0>(pp[iPar]), get<1>(pp[iPar]) - pw[iPar] - pw[cur]);
					pp[cur] = min(pp[cur], t);//经过父节点，不经过兄弟节点
					for (const auto& [f, s1, i] : pc[iPar]) {
						if ((-1 == i) || (i == cur)) { continue; }
						t = make_pair(get<0>(pc[i].front()) + ew[i] + ew[cur], get<1>(pc[i].front()) - pw[i] - 2 * pw[iPar] - pw[cur]);
						pp[cur] = min(pp[cur], t);//经过父节点，经过兄弟节点
						break;
					}
				}
				vector<pair<long long, long long>> ppc(N);
				for (int i = 0; i < N; i++) {
					ppc[i] = min(pp[i], make_pair(get<0>(pc[i].front()), get<1>(pc[i].front())));
				}
				C2Parents par2s(pars, leves);

				/*{
					vector<pair<long long, long long>> ppc1(N,make_pair(LLONG_MAX/2,0));
					for (int a = 0; a < N; a++) {
						for (int b = 0; b < N; b++) {
							const int ab = par2s.GetPublicParent(a, b);
							pair<long long, long long> abr(0,0);
							for (int i = a; i != ab; i = pars[i]) {
								abr.first += ew[i];
								abr.second += -2 * pw[i];
							}
							for (int i = b; i != ab; i = pars[i]) {
								abr.first += ew[i];
								abr.second += -2 * pw[i];
							}
							abr.second += pw[a];
							abr.second -= 2 * pw[ab];
							ppc1[a] = min(ppc1[a], abr);
						}
					}
					for (int i = 0; i < N; i++) {
						AssertEx(-ppc1[i].second, ppc[i]);
					}
				};*/
				CMultMin<pair<long long, long long>> mult(pars, par2s, ppc);
				vector<long long> ans;
				for (const auto& [a, b] : que) {
					const int ab = par2s.GetPublicParent(a, b);
					const auto curAns1 = mult.Query(a, leves[a] - leves[ab], ppc[ab]);
					const auto curAns2 = mult.Query(b, leves[b] - leves[ab], ppc[ab]);
					const auto curAns3 = min(curAns1, curAns2);
					//AssertEx(curAns3, curAns);
					ans.emplace_back(pw0[a] + pw0[b] - 2 * pw0[ab] + pw[ab] - curAns3.second);
				}
				return ans;
			}
		};
	public:
		vector<int> a;
		vector<tuple<int, int, int>> edge;
		vector<pair<int, int>> que;
		TEST_METHOD(TestMethod1)
		{
			a = { 1,1,1,1,1,1,1 }, edge = { {1,2,3},{3,6,-4},{2,5,2},{1,3,6},{2,4,1},{3,7,5} },
				que = { {4,7} };
			auto res = Solution().Ans(a, edge, que);
			AssertV(vector<long long>{ 8 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			a = { 786755,-687509,368192,154769,647117,-713535,337677,913223,-389809,-824004 },
				edge = { {1,2,-785875},{1,3,-77082},{1,4,-973070},{3,5,-97388},{2,6,-112274},{3,7,657757},{4,8,741733},{3,9,5656},{4,10,-35190} };
			que = { {3,3},{3,10},{7,3},{5,1},{2,10},{10,10},{1,6},{7,2},{8,9},{9,1} };
			auto res = Solution().Ans(a, edge, que);
			AssertV(vector<long long>{ 971424, -1257332, 1309101, 3420605, -2313033, -2567048, -2467802,
				352646, 759321, 1368370 }, res);
		}
	};

	TEST_CLASS(P10391)
	{
		//【LCA DFS 前缀和】P10391 [蓝桥杯 2024 省 A] 零食采购|普及+
		class Solution {
		public:
			vector<int> Ans(const int N, vector<int>& c, vector<pair<int, int>>& edge, vector<pair<int, int>>& que) {
				auto neiBo = CNeiBo::Two(N, edge, false, 1);
				vector<vector<int>> cnt(20, vector<int>(N)), preSum(20, vector<int>(N));
				vector<int> vpar(N, -1);
				function<void(int, int)> DFS = [&](int cur, int par) {
					vpar[cur] = par;
					for (int i = 0; i < 20; i++)
					{
						cnt[i][cur] = (i == c[cur] - 1);
						preSum[i][cur] = cnt[i][cur];
						if (-1 != par) {
							preSum[i][cur] += preSum[i][par];
						}
					}
					for (const auto& next : neiBo[cur]) {
						if (next == par) { continue; }
						DFS(next, cur);
					}
				};
				DFS(0, -1);
				auto leves = CBFSLeve::Leve(neiBo, { 0 });
				C2Parents p2(vpar, leves);
				vector<int> ans;
				for (auto [u, v] : que) {
					u--, v--;
					const int g = p2.GetPublicParent(u, v);
					int cur = 0;
					for (int i = 0; i < 20; i++) {
						cur += (preSum[i][u] + preSum[i][v] - 2 * preSum[i][g] + cnt[i][g] > 0);
					}
					ans.emplace_back(cur);
				}
				return ans;
			}
		};
	public:
		int N;
		vector<int> c;
		vector<pair<int, int>> edge, que;
		TEST_METHOD(TestMethod01)
		{
			N = 4, c = { 1,2,3,1 }, que = { {4,3},{1,4} }, edge = { {1,2},{1,3},{2,4} };
			auto res = Solution().Ans(N, c, edge, que);
			AssertEx({ 3,2 }, res);
		}
	};

	TEST_CLASS(P3833)
	{
		//【LCA 树状数组 树上差分】P3833 [SHOI2012] 魔法树|省选-
		class Solution {
		public:
			vector<long long> Ans(vector<pair<int, int>>& ab,vector<tuple<int,int,int>>& que) {
				const int N = ab.size()+1;
				vector<int> pars(N, -1);
				vector<vector<int>> vChild(N);
				for (const auto& [a, b] : ab) {
					pars[b] = a;
					vChild[a].emplace_back(b);
				}
				
				vector<int> vSort(N), vLeve(N), vEndSort(N), vSortToNode(N);
				int iTime = 0;
				function<void(int, int)> DFS = [&](int cur, int leve) {
					vSortToNode[iTime] = cur;
					vSort[cur] = iTime++;
					vLeve[cur] = leve;
					for (const auto& chi : vChild[cur]) {
						DFS(chi, leve + 1);
					}
					vEndSort[cur] = iTime - 1;
				};
				DFS(0, 0);
				C2Parents mp(pars,vLeve);
				vector<long long> ans;
				CTreeArr<long long> bit1(N), bit2(N);
				for (const auto& [u,v,d] : que) {
					if (-1 == d) {//查询
						const auto i1 = bit1.Sum(vEndSort[u]) - bit1.Sum(vSort[u]-1);
						const auto i2 = bit2.Sum(vEndSort[u]) - bit2.Sum(vSort[u]-1);
						ans.emplace_back(i1-i2*vLeve[u]);
						continue;
					}
					const int g = mp.GetPublicParent(u, v);
					bit1.Add(vSort[u], d*(vLeve[u]+1));
					bit1.Add(vSort[v], d * (vLeve[v] + 1));
					bit1.Add(vSort[g], -d*(vLeve[g]+1));
					bit2.Add(vSort[u], d);
					bit2.Add(vSort[v], d);
					bit2.Add(vSort[g], -d);
					if (-1 != pars[g])
					{
						bit1.Add(vSort[pars[g]], -d * (vLeve[pars[g]] + 1));
						bit2.Add(vSort[pars[g]], -d);
					}
				}
				return ans;
			}
		};

	public:
		vector<pair<int, int>> ab;
		vector<tuple<int, int, int>> que;
		TEST_METHOD(TestMethod01)
		{
			ab = { {0,1},{1,2},{2,3} }, que = { {1,3,1},{0,-1,-1},{1,-1,-1},{2,-1,-1} };
			auto res = Solution().Ans(ab,que);
			AssertV({ 3,3,2 }, res);
		}
	};
}
namespace NOtherMultiply {
	TEST_CLASS(P2320)
	{
		//【进制】P2320 [HNOI2006] 鬼谷子的钱袋|普及+
		class Solution {
		public:
			vector<int> Ans(int h) {
				int i = 0;
				for (; (1 << i) <= h; i++) {
					h -= (1 << i);
				}
				vector<int> ans;
				for (int j = 0; j < i; j++) {
					const int mask = 1 << j;
					if (h == mask) {
						if (1 == h) {
							ans.emplace_back(1);
							ans.emplace_back(1);
						}
						else {
							ans.emplace_back(h - 1);
							ans.emplace_back(h + 1);
						}
						h = 0;
						continue;
					}
					if ((0 != h) && (h < mask)) {
						ans.emplace_back(h);
						h = 0;
					}
					ans.emplace_back(mask);
				}
				if (0 != h) { ans.emplace_back(h); }
				return ans;
			}
		};
	public:
		TEST_METHOD(TestMethod01)
		{
			auto res = Solution().Ans(7);
			AssertEx({ 1,2,4 }, res);
		}
		TEST_METHOD(TestMethod02)
		{
			auto res = Solution().Ans(8);
			AssertEx({ 1,1,2,4 }, res);
		}
		TEST_METHOD(TestMethod03)
		{
			auto res = Solution().Ans(9);
			AssertEx({ 1,1,3,4 }, res);
		}
		TEST_METHOD(TestMethod04)
		{
			auto res = Solution().Ans(6);
			AssertEx({ 1,2,3 }, res);
		}
	};

	TEST_CLASS(P7809)
	{
		//【ST表 前缀和】P7809 [JRKSJ R2] 01 序列|普及+
		class CMyST : public CST<int>
		{
		public:
			typedef  int TSave;
			CMyST(const vector<int>& a):CST(a.size(),0){
				m_data[0].assign(a.size(),1);
				for (const auto& n : a) {
					m_pre.emplace_back(m_pre.back()+(1==n));
				}
			}
			void OnUnion(TSave& unionVal, const TSave& leftVal, const TSave& rVal, int leftIndex, int mid, int rIndex)
			{
				const int i1 = m_pre[mid + 1] - m_pre[leftIndex];
				const int j1 = m_pre[rIndex + 1] - m_pre[mid + 1];
				const int i0 = mid - leftIndex + 1 - i1;
				auto tmp = max(leftVal, rVal);
				tmp = max(tmp, i0+rVal);
				tmp = max(tmp, leftVal + j1);
				unionVal = tmp;
			}
			vector<int> m_pre = { 0 };
		};
		class Solution {
		public:
			vector<int> Ans(vector<int>& a, vector<tuple<int, int, int>>& que) {
				const int N = a.size();				
				vector<int> inxs;
				for (int i = 0; i < N; i++) {
					if (1 == a[i]) { inxs.emplace_back(i); }
				}
				auto Is01 = [&](int left, int r) {
					auto it = upper_bound(inxs.begin(), inxs.end(), r);
					if (inxs.begin() == it) { return false; }//不存在下标<=r的1
					--it;
					if (*it < left) { return false; }
					auto it2 = lower_bound(inxs.begin(), inxs.end(), left);
					if (it - it2 == *it - left) { return false; }//最后一个1之前没有0
					return true;
				};
				CMyST st(a);
				st.Init();
				vector<int> ans;
				for (auto [kind, left, r] : que) {
					left--, r--;
					const int len = r - left + 1;
					if (1 == kind) {
						ans.emplace_back(st.QueryByLen(left, len));
					}
					else {
						ans.emplace_back(Is01(left, r) ? 2 : 1);
					}
				}
				return ans;
			}
		};
	public:
		vector<int> a;
		vector<tuple<int, int, int>> que;
		TEST_METHOD(TestMethod01)
		{
			a = { 1,1,1,1 }, que = { {1,1,4} };
			auto res = Solution().Ans(a, que);
			AssertV({ 4 }, res);
		}
		TEST_METHOD(TestMethod11)
		{
			a = { 0,1,1,0,1,0,0,1 }, que = { {1,1,8},{2,1,8},{1,3,6},{2,5,6} };
			auto res = Solution().Ans(a, que);
			AssertV({ 5,2,2,1 }, res);
		}
	};


	TEST_CLASS(P10264)
	{
		//P10264 [GESP202403 八级] 接竹竿
		class Solution {
		public:
			vector<int> Ans(vector<int>& a, vector<pair<int, int>>& que) {
				const int N = a.size();
				vector<int> b(N, N), next(14, N);
				for (int i = N - 1; i >= 0; i--) {
					b[i] = next[a[i]];
					next[a[i]] = i;
				}
				const int M = 15;
				vector<vector<int>> c(N, vector<int>(M + 1, -2));
				function<int(int, int)> F = [&](int i, int len) {
					len = min(len, N - i);
					if (len <= 0) { return -1; };
					int j = 0;
					while ((1 << j) < len) { j++; }
					if (((1 << j) == len) && (-2 != c[i][j])) { return c[i][j]; }
					j--;
					auto x = c[i][j];
					const auto& len1 = 1 << j;
					if (-1 == x) { return F(i + len1, len - len1); }
					if (b[x] >= i + len)return x;
					return F(b[x] + 1, len - (b[x] + 1 - i));
				};
				for (int i = 0; i < N; i++) { c[i][0] = i; }
				for (int j = 1; j <= M; j++) {
					for (int i = 0; i < N; i++) { c[i][j] = F(i, 1 << j); }
				}
				function<int(int, int)> G = [&](int i, int len) {
					len = min(len, N - i);
					if (len <= 0) { return 0; }
					int x = F(i, len);
					if (-1 == x) { return 0; }
					return 1 + G(x + 1, len - (x + 1 - i));
				};
				vector<int> ans;
				for (const auto& [left, r] : que) {
					ans.emplace_back(G(left - 1, r - left + 1));
				}
				return ans;
			}
		};
	public:
		vector<int> a;
		vector<pair<int, int>> que;
		TEST_METHOD(TestMethod11)
		{
			a = { 1,2,2,3,1,3 }, que = { {1,3},{1,6},{1,5},{5,6} };
			auto res = Solution().Ans(a, que);
			AssertEx({ 1,1,0,2 }, res);
		}

	};

	TEST_CLASS(P11663)
	{
		//【倍增 化环为链】 P11663 [JOI 2025 Final] 勇者比太郎 2 / Bitaro the Brave 2|普及+		

		class CMyST : public CST<int> {
		public:
			typedef int TSave;
			CMyST(vector<int>& A, vector<int>& B) :CST(A.size(), 0) {
				for (const auto& n : B) { m_preSum.emplace_back(m_preSum.back() + n); }
				m_data[0] = A;
			}
			virtual void OnUnion(TSave& unionVal, const TSave& leftVal, const TSave& rVal, int leftIndex, int mid, int rIndex) override {
				const auto y = m_preSum[mid + 1] - m_preSum[leftIndex];
				unionVal = max((long long)leftVal, rVal - y);
			}
			vector<long long> m_preSum = { 0 };
		};

		class Solution {
		public:
			int Ans(vector<int>& A, vector<int>& B) {
				const int N = A.size();
				A.resize(2 * N - 1);
				B.resize(2 * N - 1);
				for (int i = N;i < A.size();i++) {
					A[i] = A[i - N];
					B[i] = B[i - N];
				}
				CMyST st(A, B);
				st.Init();
				int ans = INT_MAX / 2;
				for (int i = 0;i < N;i++) {
					ans = min(ans, st.QueryByLen(i, N));
				}
				return ans;
			}
		};
	public:
		vector<int> A,B;
		TEST_METHOD(TestMethod01)
		{
			A = { 1,3,2,8,6 }, B = { 4,3,1,1,2 };
			auto res = Solution().Ans(A,B);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			A = { 1,6,3,3,2 }, B = { 1,2,1,0,1 };
			auto res = Solution().Ans(A, B);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod13)
		{
			A = { 11,9,8,12,7,7,8,12,9,10 }, B = { 1,1,1,1,1,1,1,1,1,1 };
			auto res = Solution().Ans(A, B);
			AssertEx(9, res);
		}
		TEST_METHOD(TestMethod14)
		{
			A = { 1125,638,0,37,737,820,1202 }, B = { 23,984,558,350,52,345,580 };
			auto res = Solution().Ans(A, B);
			AssertEx(0, res);
		}
	};
}



